package LearnAlgorithm.h_标准数学公式;

public class j快速幂运算 {
	public static void main(String[] args) {
		int res1 = quickExponentiation(2, 4);//16
		System.out.println(res1);

//		int parseInt = Integer.parseInt(Integer.toBinaryString(4));
		long res2 = quickExponentiationPlus(2, 4);//16
		System.out.println(res2);
		
		try {
			long res3 = quickmatrixExponentiation(9);//34
			System.out.println(res3);
			long res4 = quickmatrixExponentiation(15);
			System.out.println(res4);
			
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/**
	 * 快速幂运算第一种形式
	 * 含有递归
	 * @param a
	 * @param n
	 * @return
	 */
	public static int quickExponentiation(int a, int n) {//a是底数；n是指数；a^n
		if (n == 1) {
			return a;
		}
		int temp = a;
		int res = 1;
		int exponent = 1;
		while ((exponent << 1) < n) {
			temp = temp * temp;
			exponent = exponent << 1;
		}
		res *= quickExponentiation(a, n - exponent);
		return res * temp;
	}
	
	/**
	 * 快速幂运算第二种形式
	 * 利用迭代
	 * @param a
	 * @param m
	 * @return
	 */
	public static long quickExponentiationPlus(long a, long m) {//a是底数；m是指数；m是2进制表示；n=10;m=1010
		long pingFangShu = a;//开始pingFangShu是a的2的0次方；即a^(2^0)；因为指针指在二进制数的从右数第一位；为第一位二进制数做准备
		long res = 1;
		while (m != 0) {//进入循环，也就是指针指在二进制数的从右数第一位
			if ((m & 1) == 1) {//二进制位判断是否为1
				res = res * pingFangShu;
			}
			pingFangShu = pingFangShu * pingFangShu;//为下一位二进制数做准备
			m = m >>> 1;//为下一位二进制数做准备；m向右移动了y次，就代表着pingFangShu = a^(2^y)；
		}
		return res;
	}
	
	/**
	 * 斐波那契数列求f(n)
	 * f(n) = f(n-1) + f(n-2)
	 * 利用矩阵的快速幂运算实现
	 * 利用迭代
	 * 这个算法的具体怎么想出来的，去看蓝桥杯6章14小节
	 * @param n
	 * @return
	 * @throws Exception
	 */
	public static long quickmatrixExponentiation(long n) throws Exception {
		if (n == 1 || n == 2) {//斐波那契数列的起始两项f(1)f(2)
			return 1;
		}
		long[][] matrix = new long[][] {//定义矩阵快速幂运算需要用的帮助矩阵
				{0, 1},
				{1, 1}
		};
		long[][] unit = new long[][] {//定义迭代入口
			{1, 1}//矩阵里面的值，就是f(1), f(2)的数值
		};
		//[f(1), f(2)] 	乘 (matrix)^(n-1) = [f(n), f(n+1)]
		//即：
		//unit 			乘 (matrix)^(n-1) = [f(n), f(n+1)] 
		long[][] res = matrixExponentiationItself(matrix, n - 1);
		res = matrixMultiply(unit, res);
		return res[0][0];//res[0][0] = f(n)
	}
	
	/**
	 * 计算一个矩阵的n次幂
	 * @param matrix
	 * @param n
	 * @return
	 * @throws Exception
	 */
	public static long[][] matrixExponentiationItself(long[][] matrix, long n) throws Exception {//n是指数；n是2进制表示；
		long[][] res = new long[matrix.length][matrix[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		//上面的代码，仅仅用来生成一个单位矩阵；相当于整数的1
		//下面的代码，逻辑上运用了“快速幂运算第二种形式”
		long[][] pingFangShu = matrix;//初始化pingFangShu；即matrix^(2^0)
		while (n != 0) {
			if ((n & 1) != 0) {
				res = matrixMultiply(res, pingFangShu);
			}
			pingFangShu = matrixMultiply(pingFangShu, pingFangShu);
			n = n >>> 1;
		}
		return res;
	}
	
	/**
	 * O(N^3)
	 * @param A
	 * @param B
	 * @return
	 * @throws Exception
	 */
	public static long[][] matrixMultiply(long[][] A, long[][] B) throws Exception {
		int Arow = A.length;
		int Acol = A[0].length;
		int Brow = B.length;
		int Bcol = B[0].length;
		if (Arow == 0 || Acol == 0 || Brow == 0 || Bcol == 0) {
			throw new Exception("输入空矩阵");
		} else if (Acol != Brow) {
			throw new Exception("两矩阵行列数乘运算不合法");
		}
		long[][] res = new long[Arow][Bcol];
		for (int currentRow = 0; currentRow < Arow; currentRow++) {
			for (int currentCol = 0; currentCol < Bcol; currentCol++) {
				for (int current = 0; current < Acol; current++) {
					res[currentRow][currentCol] += A[currentRow][current] * B[current][currentCol];
				}
			}
		}
		return res;
	}
}
